/*
 * @Author: wwssaabb
 * @Date: 2021-11-24 15:51:37
 * @LastEditTime: 2021-11-24 18:01:20
 * @FilePath: \handwritten-code\algorithm\爬楼梯.js
 */

//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。 你有多少种不同的方法可以爬到楼顶呢
console.time(1)

//递推法 空间复杂度 O(n)、时间复杂度 O(n)
// function climbStairs(n) {
//   let dp = []
//   dp[0] = 0, dp[1] = 1, dp[2] = 2 //一个台阶有一种方法 1  ，两个台阶有 1+1、2 两种方法
//   for (let i = 3; i <= n; i++) {
//     dp[i] = dp[i - 1] + dp[i - 2] //到第i阶有两种方法，i-1 +1、i-2 +2
//   }
//   return dp[n]
// }
// console.log(climbStairs(3))
// console.log(climbStairs(10))
// console.log(climbStairs(5))
// console.log(climbStairs(4))
// climbStairs(38000)

//滚动数组思想+递推 空间复杂度O(1)、时间复杂度O(n)
var climbStairs = function (n) {
  let p = 0,
    q = 0,
    r = 1
  for (let i = 1; i <= n; i++) {
    p = q
    q = r
    r = p + q
  }
  return r
};
climbStairs(38)

console.timeEnd(1)